package io.github.handyang.algorithms.graph;

import lombok.extern.slf4j.Slf4j;
import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

@Slf4j
public class GraphTest {

    private Map<Integer, Integer> prepareAdj() {
        Map<Integer, Integer> data = new HashMap<>();

        data.put(0, 1);
        data.put(2, 0);

        return data;
    }

    @Test
    public void testMatrixGraph() {
        Map<Integer, Integer> adj = prepareAdj();

        Graph graph = new MatrixGraph(3);
        adj.forEach(graph::addEdge);

        log.info("point:0, adj:{}", graph.adj(0));
        log.info("graph:{}", graph);
    }

    @Test
    public void testArrayGraph() {
        Map<Integer, Integer> adj = prepareAdj();

        Graph graph = new ArrayGraph(3);
        adj.forEach(graph::addEdge);

        log.info("point:0, adj:{}", graph.adj(0));
        log.info("graph:{}", graph);
    }

    /**
     * 5<---+0+-----> 1
     * ^     +        +
     * |     +--->2<--+
     * |     +----+
     * |     v    |
     * +----+3    +----->4
     * +           ^
     * |           |
     * +-----------+
     *
     * @return
     */
    private Graph preparePathsGraph() {
        Graph graph = new ArrayGraph(6);
        graph.addEdge(0, 5);
        graph.addEdge(2, 4);
        graph.addEdge(2, 3);
        graph.addEdge(1, 2);
        graph.addEdge(0, 1);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(0, 2);

        return graph;
    }

    /**
     * +--+0+------------->6        7+--->8
     * v   +               ^
     * 1   +------->2      |
     * |               |
     * |               |
     * |   3+----+     |        9 +----->10
     * |   ^     |     |        + |
     * v---+     v     |        | +-------+
     * 5+------->4+----+        v         v
     * 11+------>12
     *
     * @return
     */
    private Graph prepareCCGraph() {
        Graph graph = new ArrayGraph(13);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 5);
        graph.addEdge(0, 6);
        graph.addEdge(5, 3);
        graph.addEdge(5, 4);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);
        graph.addEdge(7, 8);
        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(9, 12);
        graph.addEdge(11, 12);

        return graph;
    }

    @Test
    public void testDFSPaths() {
        Graph graph = preparePathsGraph();

        Paths dfsPaths = new DFSPaths(graph, 0);
        assert dfsPaths.hasPathTo(4);

        Assert.assertEquals(Arrays.asList(3, 5, 0), dfsPaths.pathTo(3));
    }

    @Test
    public void testBFSPaths() {
        Graph graph = preparePathsGraph();

        Paths paths = new BFSPaths(graph, 0);
        assert paths.hasPathTo(4);
        Assert.assertEquals(Arrays.asList(4, 2, 0), paths.pathTo(4));
    }

    @Test
    public void testCC() {
        Graph graph = prepareCCGraph();
        CC cc = new DFSCC(graph);

        Assert.assertFalse(cc.connected(0, 7));
        Assert.assertTrue(cc.connected(8, 7));
        Assert.assertTrue(cc.connected(10, 12));
        Assert.assertEquals(3, cc.count());
        Assert.assertEquals(2, cc.id(9));
    }

    private Graph prepareCycleGraph() {
        Graph graph = new ArrayGraph(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);

        return graph;
    }

    @Test
    public void testCycle() {
        Graph graph = prepareCCGraph();
        Cycle cycle = new Cycle(graph);

        Assert.assertTrue(cycle.hasCycle());

        graph = prepareCycleGraph();
        cycle = new Cycle(graph);

        Assert.assertFalse(cycle.hasCycle());
    }

    private Graph prepareTwoColorGraph() {
        Graph graph = new ArrayGraph(13);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 6);
        graph.addEdge(0, 5);
        graph.addEdge(1, 3);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);
        graph.addEdge(4, 6);
        graph.addEdge(6, 7);
        graph.addEdge(7, 8);
        graph.addEdge(8, 10);
        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(10, 12);
        graph.addEdge(11, 12);

        return graph;
    }

    @Test
    public void testTwoColor() {
        Graph graph = preparePathsGraph();
        TwoColor twoColor = new TwoColor(graph);

        Assert.assertFalse(twoColor.isTwoColorable());

        graph = prepareTwoColorGraph();
        twoColor = new TwoColor(graph);

        Assert.assertTrue(twoColor.isTwoColorable());
    }


}
